package com.demo.jzoffer2;

import org.junit.Test;

/**
 * @author gy
 * @date 2023/03
 */
public class Test0318_01 {

    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    };

    /**
     * 解题思路：
     * 本文解法基于性质：二叉搜索树的中序遍历为递增序列；将二叉搜索树转换成一个 排序、循环、双向链表
     * 1.排序链表：节点应从小到大排序，因此使用中序遍历，从小到大访问树的节点
     * 2.双向链表：在构建相邻节点的引用关系时，设 前驱节点 pre 和当前节点 cur
     *   不仅要构建 pre.right = cur 同时要构建 cur.left = pre
     * 3.循环链表：设链表头节点 head 和尾节点 tail 则鹰钩尖 head.left = tail 和 tail.right = head
     *
     * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。
     * 要求不能创建任何新的节点，只能调整树中节点指针的指向。
     * @param root
     * @return
     */
//    public Node treeToDoublyList(Node root) {
//        return null;
//    }


    /**
     * 首先进行中序遍历，将二叉搜索树 转化为 递增序列
     * 函数功能：对二叉搜索树实现中序遍历
     */
//    public void dfs(Node cur){
//        // 寻找递归的结束条件
//        if (cur == null){
//            return;
//        }
//        // 找到函数的等价关系式 二叉搜索树实现中序遍历 = 左子树的中序遍历 + 根遍历 + 右子树的中序遍历
//        // 中序遍历 左、根、右
//        dfs(cur.left); // 遍历左子树 对左子树实现中序遍历
//        System.out.println(cur.val); // 遍历根的值
//        dfs(cur.right); // 遍历右子树 对右子树实现中序遍历
//    }

    Node head, pre;
    public Node treeToDoublyList(Node root) {
        if(root==null) return null;
        dfs(root);

        pre.right = head;
        head.left =pre;//进行头节点和尾节点的相互指向，这两句的顺序也是可以颠倒的

        return head;

    }

    /**
     * 函数功能：对二叉搜索树实现中序遍历，同时构建 双向、循环链表
     */
    public void dfs(Node cur){
        // 寻找递归的结束条件
        if (cur == null){
            return;
        }
        // 找到函数的等价关系式 二叉搜索树实现中序遍历 = 左子树的中序遍历 + 根遍历 + 右子树的中序遍历
        // 中序遍历 左、根、右
        dfs(cur.left); // 遍历左子树 对左子树实现中序遍历

        // 开始构建链表
        if (pre == null){
            head = cur;
        }else{
            pre.right = cur;
        }
        cur.left = pre; // pre是否为null 对这句没有印象
        pre = cur; // pre指向当前的cur

        dfs(cur.right); // 遍历右子树 对右子树实现中序遍历
    }

    @Test
    public void m1() {

    }

    @Test
    public void m2() {

    }

    @Test
    public void m3(){

    }

}
